1. Field of the Invention
The present invention relates to computer architectures and, more specifically, to multiprocessor computer architectures.
2. Background Information
Multiprocessor computing systems, such as symmetrical multiprocessor (SMP) systems, provide a computer environment in which software applications may run on a plurality of processors using a single address space or shared memory abstraction. In a shared memory system, each processor can access any data item without a programmer having to worry about where the data is or how to obtain its value. This frees the programmer to focus on program development rather than on managing partitioned data sets and communicating values.
In multiprocessor computer systems, resources may be shared among the entities or “agents” of the system, such as processors, memory controllers or input/output (I/O) interface devices. Operation of a multiprocessor computer system involves the passing of messages or packets as transactions between the agents of the system. System resources, moreover, are typically configured to support a maximum bandwidth load that may be provided by the agents. In some cases, however, it is not practical to configure a resource to support peak bandwidth loads especially where those conditions are expected to arise only infrequently, i.e., only in the presence of unusual traffic conditions. Resources that cannot support maximum system bandwidth under all conditions require complimentary flow control mechanisms that disallow the unusual traffic patterns resulting in peak bandwidth.
In a credit-based or window flow control system, a receiver gives N credits to a sender. Each time the sender issues a message to the receiver, the sender decrements the number of available credits. As the receiver drains messages from its buffer, it sends new credits to the sender. Thus, the existence of a credit at the sender represents space in the receiver's buffer for accepting a new message. If the number of credits reaches zero, the sender stops issuing messages to the receiver.
FIG. 1 is a block diagram of a multiprocessor computer system 100 organized as a torus. The system includes a plurality of processor nodes (N) 102a–i that are interconnected by a plurality of links 104a–l that, together with buffering resources, form an interconnection network. Each processor node 102a–i may further include local memory and input/output (I/O) resources not shown that are available to the other processor nodes. To exchange information, packets are sent among the processor nodes via the links 104a–l. In particular, each processor node may further include a routing agent (not shown) that receives packets from the other nodes and forwards those packets that are destined for a processor node other than the routing agent's local processing node. The nodes may also include one or more buffers, such as buffers 106a–d at nodes 102a (N0), 102b (N1), 102d (N3) and 102e (N4), respectfully, for buffering packets that have been received at the respective node and that are to be forwarded to some other node.
To select the particular path along which a packet will travel through the interconnection network, the system 100 utilizes a routing function. The routing function may be implemented by a routing algorithm executed by the nodes, or it may be specified in preprogrammed routing tables located at the nodes. The routing function may be static, meaning that the same path is used for every pair of source and destination nodes, or it may be dynamic, in which case, two packets traveling between the same two nodes may nonetheless use different paths, e.g., to avoid congestion. Typically, a shortest path is selected to reduce latency. The routing function may identify a set of output channels for a given packet that in turn defines the path to be taken. In this case, an output selector function is employed to choose one of the identified channels for the given packet. Depending on the topology of the interconnection network and the choice of the routing function, it is possible that one or more cycles will exist among the many paths defined by the routing function. These cycles are also known as loops.
As mentioned above, flow control mechanisms are often applied to the interconnection network of a computer system, e.g., to links 104 of computer system 100. These flow control mechanisms ensure that resources, such as sufficient space in a buffer, exist at a receiving node before a sending node is permitted to send a packet. If the receiving node's buffer is currently full, the flow control mechanism blocks the sending node from issuing the packet. If the interconnection network contains one or more cycles or loops, then the blocking of packets can result in deadlock.
More specifically, suppose node 102a (N0) has a packet to send to node 102e (N4) and, pursuant to the routing function implemented by system 100, this packet is to travel via node 102b (N1). Suppose further that node 102b (N1) has a packet to send to node 102d (N3) via node N4, that node 102e (N4) has a packet to send to node 102a (N0) via node N3, and that node 102d (N3) has a packet to send to node 102b (N1) via node N0. Suppose further that buffer 106b at node 102b (N1) is full of packets all targeting node N4, that buffer 106c at node 102e (N4) is full of packets targeting node N3, that buffer 106d at node 102d (N3) is full of packets targeting node N0, and that buffer 106a at node 102a (N0) is full of packets targeting node N1. Due to flow control requirements, the full buffer condition at buffer 106a precludes node N3 from sending any additional packets to node N0. Likewise, the full buffer conditions at buffers 106b–d precludes nodes N0, N1 and N4, respectively, from sending any additional packets. This loop is an example of a circular routing deadlock condition.
One method of avoiding circular routing deadlock is to design the interconnection network to be free of any loops. Some interconnection networks, such as certain tree architectures, are inherently loop-free. Other interconnection networks can be rendered loop-free by fixing the routes that packets must travel between various entities of the computer system. That is, the routes are selected to avoid the formation of any loops. If, for example, the routing function implemented by computer system 100 specified that the path utilized for packets travelling from node N0 to node N4 goes through node N3 rather than node N1, the circular routing deadlock condition described above would be avoided. Although this approach avoids circular routing deadlock, it significantly limits the design of the interconnection network. Indeed, for some complex topologies, such as those having large numbers of processors, it may not be possible to eliminate all of the loops. The requirement of loop-free designs may also preclude the computer system from employing an adaptive routing scheme in which the routing paths can be changed dynamically to avoid congestion.
Another solution to avoiding circular routing deadlock is described in L. Natvig “High-level Architectural Simulation of the Torus Routing Chip”, Proceedings of the International Verilog HDL Conference, March–April 1997. Here, time lines and extra virtual channels are added to the interconnection network. Specifically, one or more time lines are logically drawn or imposed onto the system breaking the loops. Furthermore, for each physical (or virtual) channel, a new virtual channel is established. For example, if the system has virtual channels 1, 2 and 3, then new virtual channels 1a, 2a and 3a are established. Whenever a message crosses one of the time lines, it is moved from its current virtual channel into a selected one of the new virtual channels.
Referring to FIG. 1 again, a time line 110 may be placed on link 104a breaking the loop identified above. Messages traversing link 104a are moved from their current channel to one of the newly created channels. For example, a message in virtual channel 2 at node 102a (N0) that is to be transmitted across link 104a is placed in a new buffer (not shown) at node 102b (N1) that corresponds to virtual channel 2a. By drawing the time lines at appropriate places within the interconnection network, circular routing deadlock can generally be avoided.
The addition of a second set of virtual channels, however, increases the complexity of the computer system and requires the deployment of greater resources, which typically increases the cost. Furthermore, in some cases, such as when using industry standard components, it may not be possible or practical to establish new virtual channels. Accordingly, a need exists for an alternative system and method for avoiding deadlock.